package main

import (
	"container/heap"
	"strconv"
)

func main() {
	// [1047. 删除字符串中的所有相邻重复项](https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/)
	// [150. 逆波兰表达式求值](https://leetcode.cn/problems/evaluate-reverse-polish-notation/)
	// [239. 滑动窗口最大值](https://leetcode.cn/problems/sliding-window-maximum/)
	// [347. 前 K 个高频元素](https://leetcode.cn/problems/top-k-frequent-elements/)
}

// 1047
func removeDuplicates(s string) string {
	stack := make([]byte, 0)
	for i := range s {
		if len(stack) == 0 || s[i] != stack[len(stack)-1] {
			stack = append(stack, s[i])
		} else {
			stack = stack[:len(stack)-1]
		}
	}
	return string(stack)
}

// 150
func evalRPN(tokens []string) int {
	stack := make([]int, 0, len(tokens))
	for i := 0; i < len(tokens); i++ {
		val := tokens[i]
		switch val {
		case "+", "-", "*", "/":
			n, m := stack[len(stack)-2], stack[len(stack)-1]
			stack = stack[:len(stack)-2]
			switch val {
			case "+":
				stack = append(stack, n+m)
			case "-":
				stack = append(stack, n-m)
			case "*":
				stack = append(stack, n*m)
			case "/":
				stack = append(stack, n/m)
			}
		default:
			v, _ := strconv.Atoi(val)
			stack = append(stack, v)
		}
	}
	return stack[0]
}

// 239
func maxSlidingWindow(nums []int, k int) []int {
	ans := make([]int, len(nums)-k+1)
	q := make([]int, 0)
	var push func(x int)
	push = func(x int) {
		for len(q) > 0 && q[len(q)-1] < x {
			q = q[:len(q)-1]
		}
		q = append(q, x)
	}
	for i := 0; i < k; i++ {
		push(nums[i])
	}
	ans[0] = a[0]
	for i := 1; i < len(nums)-k+1; i++ {
		if nums[i-1] == q[0] {
			q = q[1:]
		}
		push(nums[i+k-1])

		ans[i] = q[0]
	}
	return ans
}

// 347
func topKFrequent(nums []int, k int) []int {
	//堆
	map_num := map[int]int{}
	for _, v := range nums {
		map_num[v]++
	}
	h := &IHeap{}
	heap.Init(h)
	for key, val := range map_num {
		heap.Push(h, [2]int{key, val})
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	res := make([]int, k)
	for i := 0; i < k; i++ {
		res[k-i-1] = heap.Pop(h).([2]int)[0]
	}
	return res
}

type IHeap [][2]int

func (h IHeap) Len() int           { return len(h) }
func (h IHeap) Less(i, j int) bool { return h[i][1] < h[j][1] }
func (h IHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *IHeap) Push(x interface{}) {
	*h = append(*h, x.([2]int))
}

func (h *IHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

//排序
ans := make([]int, 0)
map_num := map[int]int{}
for _, v := range nums {
    map_num[v]++
}
for key, _ := range map_num {
    ans = append(ans, key)
}
sort.Slice(ans, func (a, b int) bool {
    return map_num[ans[a]] > map_num[ans[b]]
})
return ans[:k]
